Liar: an Algol-like Compiler for Scheme

by

Guillermo Juan Rozas

Submitted to the Department of Electrical Engineering and Computer Science in partial fulfillment of the requirements for the degree of

Bachelor of Science in the field of Electrical Engineering and Computer Science

at the

MASSACHUSETTS INSTITUTE OF TECHNOLOGY

June 1984

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1984 by Massachusetts Institute of Technology

Signature of Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Department of Electrical Engineering and Computer Science January 24, 1984

Certified by. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

James S. Miller

MIT AI Laboratory Research Scientist Thesis Supervisor

Accepted by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

David Adler

Chairman, Departmental Committee

ii [This page intentionally left very nearly blank.]

Liar: an Algol-like Compiler for Scheme by Guillermo Juan Rozas

Submitted to the Department of Electrical Engineering and Computer Science on January 24, 1984 in partial fulfillment of the requirements for the degree of Bachelor of Science in the field of Electrical Engineering and Computer Science

Abstract

The purpose of this thesis is to explore the features of Scheme which make its compilation harder than that of other languages, and to design a compiler which taking these features into account produces object code for a Scheme program similar to that produced by an Algol compiler for the equivalent Algol program.

The compiler consists of a program analyzer and a code translator which makes use of the information provided by the analyzer. All of these programs are written in Scheme.

Thesis Supervisor: James S. Miller Title: MIT AI Laboratory Research Scientist iv

[This page intentionally left very nearly blank.]

Acknowledgments

I would like to acknowledge the contributions and support to this work of the following people:

• James S. Miller, who is not only my thesis supervisor, but a good friend, and would tolerate my unparsable verbal core-dumps with the utmost patience. Many ideas came out of talks with him and his continued help and interest made it worth while;

• Jon D. Taft, who not only proof-read the unreadable repeatedly, and encouraged me, but who gave up his office for two weeks;

• Chris Hanson, who would question everything and make me think things out more carefully. He provided the overall perspective and a lot of good ideas;

• Gerald J. Sussman and Harold Abelson, who made 6.001 and Scheme into what they are. Five minutes of their time are worth many days of thought;

• The Scheme Team, who would tolerate my abuse and encourage me;

• The residents of 7ai, who provided an excellent environment;

• My friends, not otherwise mentioned above, who would tolerate me even when in a bad mood;

• And, last but not least, my family, who have so much confidence in me that they are going to be badly disappointed one of these days. vi

[This page intentionally left very nearly blank.]

Contents

1 Introduction 1

2 Interaction with the Scheme Interpreter 5

3 Overview of the Compiler 9 3.1 Pre-Pass . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Code generation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.4 Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 The Program Analyzer 13 4.1 Taxonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.2 Need for the analyzer . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.3 The core of the analyzer . . . . . . . . . . . . . . . . . . . . . . . . . 15 4.4 The closure analyzer . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4.5 Compile-time known variables . . . . . . . . . . . . . . . . . . . . . . 18

5 Code Generation 21 5.1 Environments and variable references . . . . . . . . . . . . . . . . . . 21 5.2 Procedures and environment linkage . . . . . . . . . . . . . . . . . . . 23 5.3 Combinations and tail recursion . . . . . . . . . . . . . . . . . . . . . 23

6 Conclusions and Comparisons with Other Work 33 6.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 6.2 Comparisons with Rabbit . . . . . . . . . . . . . . . . . . . . . . . . 33

7 Future Work 35 7.1 Improvements to the Analyzer . . . . . . . . . . . . . . . . . . . . . . 35 7.2 Improvements to the code generator . . . . . . . . . . . . . . . . . . . 37

A Scode Description and Source Code 41 A.1 Brief Scode Description . . . . . . . . . . . . . . . . . . . . . . . . . . 41 A.2 Analyzer Source Code . . . . . . . . . . . . . . . . . . . . . . . . . . 43 viii CONTENTS

[This page intentionally left very nearly blank.]

Chapter 1

Introduction

Scheme is a computer language of the Lisp family originally designed by Gerald J. Sussman and Guy L. Steele Jr. [Steele & Sussman 75] [Rees & Clinger 86]. This compiler makes tacit use of the definition of Scheme implicit in the Scheme Manual [Hanson 91]. Some of the similarities between Scheme and other Lisp dialects are the rich set of operations to manipulate symbols and list structure, the existence of (and emphasis on) an interactive interpreter to execute Scheme programs and the functional syntax. There are however many important differences between Scheme and most dialects of Lisp which make it unique. The most important of these differences are as follows:

• Scheme is a block structured language (the scope of variables is lexical rather than dynamic as in most Lisp dialects). Procedures can be declared inside of other procedures, and a variable binding is in effect within all subprocedures of the one in which the variable is declared (except for those which declare a variable of the same name).

• Procedures are first-class data objects in Scheme. Arguments to procedures and the values returned by them may be procedures themselves. Any variable may hold a procedural value at any moment of a computation and procedures can be part of other data structures. Funargs (functional arguments, procedures passed as arguments to other procedures) are widely used. They provide a simple tool to build a message passing system and are the mechanism used in the powerful continuation-passing style. Procedures are implemented as closures, that is structures with two components: a piece of program text and an environment (the environment active at the construction of the closure). See Moses [Moses 70] for a description of the funarg problem in other dialects of Lisp.

• Environments (name spaces) are first-class data objects. The collection of variable bindings in effect at any moment of a computation can be obtained and passed to procedures as an argument or returned as a value. There are primitives in the language to deal with environments.

• The main primitive control structure is provided by procedure application (function call). Loops and more complicated control structure are usually expressed in terms of procedure applications. Sussman and Steele [Steele & Sussman 76] [Steele 77] discuss how arbitrary control structure can be achieved by using procedure application and be as efficient as if special constructs were provided.

• The main primitive declarative structure is the procedure. Local (auxiliary) variables are usually declared by invoking a procedure (whose formal parameters are the desired variables) on their initial values. Code that uses internal definitions can be translated into code without them (but with assignments) in this manner. The compiler assumes that this transformation, called Scan Out Defines, has been applied to the code to be compiled. Steele [Steele 76] discusses the expressive power of lambda.

• Scheme is tail recursive. At any moment during the execution of a computation, only the information needed to continue the computation is saved. When a procedure is invoked, its caller is present only if it needs the value returned by the invoked procedure to proceed. This matter will be treated at great length in section 5.3.

Because of the use of procedure application to express many different control structures, and the possibility of implementing these in different ways with varying efficiency, it becomes imperative to recognize each case in order to translate it appropriately. This task is greatly simplified in other languages since they provide different syntax for each of the constructs.

The first problem that becomes apparent when designing a compiler for Scheme is to detect which variables hold procedural values and which procedures are their values. This may seem to have a trivial local solution (the only information needed is that given by variable definitions). It is simple to find those definitions where the defining expression is an explicit procedure, but since procedures are ordinary data in Scheme, the general case is not quite so simple. For example, in the sequence

(define (foo x y) (* x y))
(define bar foo)
(print (bar 3 4))

bar is used as a synonym for foo. It would be desirable to implement a function call to (the value of) bar as a transfer of control to the procedure initially assigned to foo, without the overhead of a variable reference. However in the following (similar) sequence

   (define (foo x y) (* x y))
   (define bar foo)
   (if (= z 5) (set! bar +))
   (print (bar 3 4))

this cannot be done. Clearly some form of data flow analysis is needed to determine compile-time known procedures.

Another problem due to funargs (first-class procedure data) is that environments cannot, in general, be allocated in a stack-like manner. The frame corresponding to a procedure may be returned explicitly as a value or implicitly (as part of a closure). If a procedure returns a procedure closed (declared) within its body, the frame corresponding to the former cannot be popped since it is part of the environment of the latter. It is necessary to decide which procedures are passed as arguments to other procedures or returned as values so that the environment where they are closed may be constructed on the heap.

The simplest solution to this problem is to construct all environments on the heap. This is, however, not an optimal solution. When environments are created in the heap, a memory reclaiming technique must be used.^{1} There are also efficient mechanisms for variable lookup (Displays) which can be used only if environments can be allocated in the stack in an Algol-like manner.

In the rest of this thesis these features and problems will be discussed in more detail as well as possible solutions and an overview of the actual compiler.

1See page 6 for the interaction between compiled code and the memory reclaiming mechanism of the interpreter.

4 CHAPTER 1. INTRODUCTION [This page intentionally left very nearly blank.]

Interaction with the Scheme Interpreter

Scheme is a language which is primarily interpreted. Compiled code is therefore designed to run within the context of the interpreter rather than stand-alone.^{1} Compiled code may therefore call procedures which are not compiled and vice-versa. There arise therefore some issues of compatibility which will be explored later.

The main features of the Scheme environment are:

• The interpreter is interactive. When a user types an expression to the interpreter (which when not executing user code is waiting for input), the expression is evaluated (executed) and its value is printed on the console. The interpreter waits again for input.

• When input is typed there is a first processing stage which converts the external representation (in characters) into an internal format (list structure) which can be manipulated more easily by Scheme programs. The program which does this conversion is called the reader, and the process reading.

• There is a second processing stage in which the syntax of the expression (now represented as list structure) is analyzed and the expression is transformed into a different format (Scode^{2}). Both the interpreter and the compiler deal with the code in Scode form instead of the external representation. This stage is called syntaxing and the program that performs it is called the Syntaxer. The default Syntaxer scans out defines^{3} except in the version of Scheme available to 6.001 students.^{4} The expression is represented as a tree where each node is an Scode structure. Scode structures correspond to the core special forms of the language and allow for faster recognition and dispatch by both the interpreter and the compiler.

1Stand-alone code is that which needs nothing but itself to run. Few compilers produce completely stand-alone code since most assume certain facilities available from a library. In the case of Scheme it can be said that the whole interpreter is the library.

2Pronounced: “S” code 3See the Introduction for a description of Scan Out Defines.

• When the interpreter first starts accepting expressions, they are evaluated in a Scheme environment (name space) where there is a set of predefined procedures. The Syntaxer provides a set of special forms to combine these procedures. The user may then define new procedures which are added to the environment. These, in turn, can be used together with the initially available procedures to define others.

• The interpreter includes a garbage collector which is invoked whenever there is a shortage of space stopping all processing until the garbage collector is done. The garbage collector understands several basic data types (corresponding primarily to small integers, pairs of objects and vectors of objects). All structures generated by the interpreter must be compatible with the garbage collector conventions. Compiled code must also generate compatible structures if they are to be returned to the interpreter or passed to interpreted procedures as arguments. This is accomplished in a simple manner. The compiler generates code which manipulates data in the same way the interpreter would. All internal manipulation of these data structures is left to the primitive operations which know how to deal with the garbage collector on an individual basis.

The presence of the interpreter during the execution of compiled code allows the compiler to ignore certain issues which are important in a stand-alone compiler:

• Few primitives must be open coded. A procedure is said to be open coded when its definition (text) is inserted at the place where it is invoked in the caller program, rather than code to invoke it. The compiler can generate calls to primitive procedures and to routines internal to the interpreter to accomplish certain complicated tasks. Most primitives are dealt with in this way. The only open coded primitives are those which are simple, common, and for which the overhead of invoking the interpreter is too large. Some of these are car, cdr,

and cons.

• There is always an error handling mechanism present. When an error occurs (which can only really occur within a primitive since these are the only procedures which manipulate internal structure), the error handling mechanism of the interpreter can be invoked to take appropriate action.

46.001 is the undergraduate introductory computer science course at MIT. It uses the textbook [Abelson & Sussmans 85].

• Interactive debugging of partially compiled systems is possible. Since compiled code can call interpreted code and vice-versa, some procedures may be compiled but not the rest, allowing greater control over them. Therefore the solid and computationally intensive parts of a system may be compiled leaving the parts under development interpreted so that they can be modified interactively.

There are, however, some disadvantages in having the interpreter:

• It is not an error to reference a variable which is not declared in the code to be compiled. The variable may be present in the interpreter environment when the compiled code is run. An appropriate warning message can be printed, however.

• Number of arguments mismatches may not always be detected at compile time since nothing may be known about the procedure being called. Compiled code can, however, generate code to use the interpreter’s procedure calling mechanism which will detect these problems.

• Open coded primitives may cause errors which can crash the system. Some type and range checking is eliminated from open coded primitives to increase the speed of the resulting code. If data which does not comply with the conventions adopted is used, the primitive may kill the system (cause a non-existent memory trap, overwrite some code, or violate a garbage collector convention) since the exception will not be caught by the interpreter error mechanism. If open coded primitives are made to include all the safe guards, the performance of compiled code may not be acceptable.

• Environments generated by compiled code and given to interpreted code (returned as values or passed as arguments) must be similar to those the interpreter generates since interpreted code may then reference variables in them. The compiler therefore cannot always choose the format of an environment and it becomes important to recognize those cases where environments are treated as data.

8 CHAPTER 2. INTERACTION WITH THE SCHEME INTERPRETER [This page intentionally left very nearly blank.]

Overview of the Compiler

The compiler is organized into various subprograms (phases) with different tasks.

There is a top level which provides overall control and communication between the different phases. The top level also provides a common environment in which utility procedures are defined and made available to all the subprograms. Communication between the phases is accomplished not only through the parameters to each of them, but also through annotations to the code being compiled. The mechanism for this annotation is also contained in the top level.

3.1 Pre-Pass

The first phase is a pre-pass on the code which makes the task of the analyzer (phase 2) considerably simpler. It consists of a recursive tree walk (code walk) and it generates the following information:

Code Copy

A copy of the original code in which all bound variables (variables declared as parameters or auxiliaries of some procedure) are renamed is made. This process, alphatizing, guarantees that there are no naming conflicts (no two variables have the same name). It is then very simple to attach information to variables since variables which originally had the same name but were declared in different procedures will now have different names. The annotation mechanism can then be built on top of the property-list mechanism available in Scheme and be reasonably fast. This new copy of the code is then used by the other phases instead of the original version.

Block Information

A tree which corresponds to the block structure (lexical structure) of the code is created. This tree, the block information structure, contains a node for each of the procedures which appear in the code and represents the procedure nesting of the code. Each node has as its subnodes the nodes corresponding to the procedures declared within it. Each node contains information on all of the (now renamed) variables which are referenced within the corresponding procedure. It is used to store the mapping between the old names and the new names so that the same new name will be used for all references to the same variable. It is also used to keep track of all the references to each of the variables and the types of references. Information on variable references is needed for the closure analysis (phase 2) and references are classified into four types: operator, operand, assignment, and other (called value).

Environment Usage

The closure analyzer needs to know which procedures deal with their environment as data and this can be determined easily in the code walk. A procedure can get hold of its environment only if the special form the-environment appears in its code, and the code walk will determine this trivially (it will find a node where the expression is (the-environment)). This information is then attached to the block information structure for later use.

Closure Information

The special form delay creates an object (delayed object) which contains a pointer to the environment active where the form appears. The closure analyzer needs to know about uses of delay since they force the procedure where they appear to create an actual environment object which can then be used to create the delayed object. The information is attached to the block information structure.

The first phase also performs some minor local source level (Scheme) optimizations. These optimizations enable the code to execute slightly faster (even when interpreted). The optimizations consist of the following:

• Elimination of unreachable conditional branches (the condition is constant). This is a useful optimization since it is often the case that experimental code contains debugging switches. The overhead of testing these switches can therefore be eliminated at compile time if the switches are known (declared) constants.

• Folding of explicit constants. If a known constant procedure (i.e., a primitive or a simple interpreted procedure like cadr or +) is applied to constant arguments, the operation can be done once and the result can be used instead of having the code compute it every time. This transformation is subject to the knowledge the compiler has about side effecting primitives. Side effecting primitives are not folded since the code may depend on the side-effect occurring at a specific point in the code. For example, if the code contains the expression

     (ERROR "This is a bug" 'BUG)

clearly the procedure and the arguments are constants, but the application cannot be done at compile time since the expression appears exclusively for effect.

• Transformation of definitions of auxiliary variables into assignments. Auxiliary variables are those declared by definitions inside of the code and which have been Scanned Out. Compiled code will deal with assignments and definitions very differently and this transformation enables the code generator to recognize each of the cases easily. Note that it is non-sensical to have a definition as the last form in a procedure, therefore there is no problem transforming definitions into assignments (which can be used for value, while definitions should not). The code generator will recognize assignments which are used for their value and deal with them appropriately.

3.2 Analysis

The code analyzer is described in detail in a following chapter. Its purpose is to determine compile-time known information and make it available to the code generator and to a possible source level optimization post-pass.

3.3 Code generation

The code generator is the subject of another chapter. It translates the code (possibly optimized by the post-pass) from Scode form into an abstract assembly language which can then be assembled on different machines. One of the main objectives in the design of a compiler is to make it machine independent enough that it can be transported easily to a different machine while not sacrificing performance for generality. The abstract assembly language helps along these lines.

3.4 Assembly

The assembler translates the output of the code generator into machine language for the target machine (in this case the Motorola MC68000 microprocessor), and links it into the system.

The assembler used was first written by James S. Miller for a previous Scheme compiler. Additions have been made to implement the linking instructions and new addressing modes generated by the code generator.

12 CHAPTER 3. OVERVIEW OF THE COMPILER [This page intentionally left very nearly blank.]

The Program Analyzer

The analyzer is invoked after the pre-pass finishes. It creates some internal data structures that it uses to accomplish its task. Its purpose is three-fold:

1. To determine the type of procedure for each procedure that appears in the code.

2. To determine which combinations have constant (fixed) operators and provide this knowledge to the code generator which will then decide how to translate each combination individually.

3. To determine which variables hold constant values.

The information provided by the analyzer is needed by the code generator to optimize procedure applications. If the invoked procedure is known at compile time, the arguments can be stored in the appropriate kind of environment immediately after they are evaluated. In this way the overhead of calls to unknown procedures can be eliminated. The callee will not have to reshape its frame after its code is entered.

4.1 Taxonomy

Procedures can be divided into groups according to how they manipulate their environment. Environments are sequences of environment frames chained together.^{1} When a procedure is applied, a new frame is constructed to contain the actual arguments. This frame is linked to the environment of declaration of the procedure. It is in this way that the lexical scoping of the language is implemented. Environments can be returned implicitly as a part of a closure, or explicitly by evaluating (the-environment). The following terminology will be used to describe procedures:

1See section 5.1 for an explanation of how frames are linked

• Open procedures Procedures whose frame is only needed while they are active (their code is being executed). They do not return their environment as a value or give it to other procedures as an argument.

• Intermediate procedures Procedures whose subprocedures (if any) are open, but which are passed along as arguments or returned as values and must therefore carry their environment of declaration with them.

• Heap closures The frame created by heap closures when applied may be needed after they become inactive. These procedures, or their subprocedures, pass their environments to code outside of them.

The above types are mutually exclusive. The following terms refer to subtypes and supertypes of them which are often used in this thesis. Some of them are taken from Steele [Steele 78].

• Interpreter compatible procedures These are all heap closures which explicitly manipulate their environment as data. They, or some subprocedure, execute a

(the-environment) within them.

• Closures These are procedures which are either heap closures or intermediate procedures. They carry their external environment along with them.

• Stack procedures These procedures are either open or intermediate procedures. Their arguments can be passed on a stack since no pointers to their environments are needed by them or their subprocedures.

• Full closures These are closures which consist of both a piece of code (entry point) and an environment. They may be called from the interpreter or from pieces of code which may call different procedures at different times.

• Partial closures These are all closures which do not need to carry their code (entry point) with them. They are called only from places which always call them and which know their address, therefore the closure need not contain its entry point. They are always ancestors or siblings of full closures.

From the point of view of the analyzer there are only four interesting types of procedures (all of which are mutually exclusive). These types are interpreter compatible procedures, full closures, partial closures, and open procedures. The analyzer assigns each procedure to one of these classes and, using this knowledge, determines compile time known operators and variables. The code generator can deduce whether a procedure belongs to one of the other types from the information provided by the analyzer.

4.2 Need for the analyzer

The problem in deciding which combinations have constant operators is that procedures are first-class data objects. For example, in

   (define (cps-fact z)
     (define (fact n cont)
       (if (zero? n)
           (cont 1)
           (fact (-1+ n) (lambda (m) (cont (* n m))))))
     (fact n (lambda (res) res)))

no call to cont can be implemented as a jump to a point in the code known at compile time since the variable cont may take more than one value. On the other hand, in

   (define (my-member list1 list2)
     (define (mem-maker predicate)
       (define (me obj list)
         (cond ((null? list) '())
               ((predicate obj (car list)) list)
               (else (me obj (cdr list)))))
       me)
     (define member (mem-maker equal?))
     (define memq   (mem-maker eq?))
     (disjunction (memq   list1 list2)
                  (member list1 list2)))

it would be desirable if the call to memq and the call to member were both translated as branches to me (even though a variable lookup would have to be done to extract the closure).

It is necessary to determine which variables have procedural values and what procedures they may be. Some simulation of runtime execution must be done to find where each procedure may ultimately be applied.

4.3 The core of the analyzer

The analyzer attempts to determine the information available at compile time. It creates a directed graph in which two variables are connected if there is a path which will make the second receive the value of the first. Procedure application generates new edges, and the graph is complete when it is closed under application. Additional variables are created as place holders, to provide a mechanism by which application is simulated.

Each node in the graph represents a variable which can be real or generated by the analyzer. Each node contains the following information:

• The variable which corresponds to the node.

• A list of backward links. This is a list of all the variables whose values the node may inherit along some path.

• A list of forward links. This is a list of all the variables which may inherit the node’s value.

• A list of all procedures which can be the value of the current node.

• A list of all constants which can be the value of the current node.

The initial (generating) subset of the graph is computed by performing a single code walk. At each node there is a variable which is expecting the value of the current expression. This variable is called the waiting variable and will (conceptually) receive the value of the expression when executed. It may not receive it in practice if it is a variable generated by the analyzer.

When combinations are encountered, additional variables are created for the operator, the operands, and for the result. An edge is established between the waiting value and the variable created as a place holder for the result: the waiting value becomes a forward link of the result and the latter a backward link of the former. Each of the operands (and the operator) is recursively walked over with the corresponding generated variable expecting its value.

Each time an Scode lambda (expression) is encountered, it is added to the procedure list of the waiting variable. A new variable is created as a place holder for the value returned by the procedure represented by the lambda expression (the procedure that would be generated by the interpreted when the lambda expression was evaluated). The body of the lambda expression is walked over with the generated variable waiting for the value that the procedure would eventually return. The zeroth formal of the procedure (the internal procedure name), also adds the procedure to its procedure list. Note that the zeroth formal of a procedure cannot be assigned, so this variable has a fixed value.

When an assignment is found, a link is established between the waiting variable (if any) and the variable being assigned. The expression for the value of the assignment is walked with the variable being assigned as the waiting variable.

When a constant is encountered, it is added to the constants list of the waiting variable.

Special forms are treated in a way analogous to the way they would be treated if evaluated. For example in a sequence the last form has the same waiting variable as the whole expression but the middle actions have no waiting variable. This corresponds to the action of the interpreter which ignores the values of all subforms but the last. The other special forms are dealt with analogously.

When all of the code has been walked, the generating set of edges has been computed. The transitive closure of the graph is then computed as follows:

• All paths are traced without making use of application. A link is established between all backward links of a variable and its forward links. The procedures and the constants are propagated along the new links.

• When the graph is closed under the previous operation (no more links can be established), application is simulated.^{2} Each combination is examined, and the following steps are taken for each procedure in the procedure list of the operator place holder:

– Links are established between the formal parameters of the procedure and the corresponding place holders for the operands.

– A link is established between the place holder for the result of the combination and the place holder for the result of the procedure.

– Consistency between the number of formal parameters and actual arguments is checked.

• Then the first step is repeated again to generate the transitive closure of the new graph. The second step is then repeated and so on until no new edges can be established through application.^{3}

At the end of this process each node in the graph contains all procedures and constants which may get to the node during the execution of the code, except for what the interpreter may pass as an argument or return as a value, but this is dealt with differently. This process is guaranteed to complete since any node may at most be linked to all others. If this condition were reached, no new links could be established, and the analysis would end.

4.4 The closure analyzer

The closure analyzer classifies all procedures which appear in the code making use of the information stored in the graph.

Interpreter compatible procedures are detected on the first pass of the compiler. They only depend on whether the form (the-environment) is found in their code.

2It is interesting to note that both steps have close resemblance to the two phases of the interpreter: eval and apply respectively. It is this remark which gives the compiler its name since “Liar imitates apply repeatedly”.

3To increase the speed of the analyzer both phases occur simultaneously. Every time a new link is established, it is traced completely both ways. On every iteration of the application loop, only those combinations which may have been affected by the previous iteration are examined.

If a procedure is interpreter compatible, so are all its ancestors. This is because a variable not contained in its frame but referenced in its code will be searched for in previous frames by the interpreter, but these frames are created by its ancestors.

The closure analyzer determines which of the procedures are closures. If a procedure is a closure, whether partial or full, so are all its ancestors and siblings, since the environment of a procedure is not only the innermost frame but also all the previous frames. If the frame is passed around, it should carry the previous frames with it, but this can only be done if all the closure’s ancestors were closures themselves and their frames are in the heap. After this analysis all procedures which are neither closures nor interpreter compatible are open since their frames are not needed after they become inactive.

Full closures are procedures which are returned as values by other procedures, are passed as arguments to other procedures, or which are called from a combination where the operator is not determined (there is more than one possible operator). All procedures declared at the top level of the code (not subprocedures of others) are also full closures since they will be available from the interpreter.

Partial closures are all those closures which are not full closures. They are all declared in environments which may be returned but not directly by them. For example, all siblings of full closures, which are not full closures themselves, are partial closures.

The algorithm for determining which procedures are closures is simple. Any procedure which appears in the procedure list corresponding to a result place holder for a procedure must be fully closed since it may be returned by the latter procedure. Similarly, any procedure which appears in the procedure list of an operand in a combination must be fully closed since it may be used as an argument. The result place holders of all procedures, and the operand place holders of all combinations, are therefore examined to determine which procedures must be fully closed. When a combination is examined, if the operator place holder has more than one procedure in its procedure list, all of them are tagged as full closures also. This last decision is not optimal but it makes the task of the code generator considerably simpler since otherwise there would have to be code to deal with each of the possibilities individually. This constraint appears because of the tail recursion algorithm explained in section 5.3.

Once all full closures have been found it is trivial to tag all their ancestors and siblings as partial closures if they have not been found to be full closures.

4.5 Compile-time known variables

At the same time that closure of procedures is analyzed, an important property of variables is examined. Variables which may be bound by an application which occurs in interpreted code cannot be known at compile time. This property is easy to check.

If a procedure is interpreter compatible, no formal parameter of any subprocedure may be known. The reason for this is that these environments are available from the interpreter and therefore these procedures may be called, via the interpreter, with any values. If a procedure is passed as a parameter to a primitive, or appears as an operand of a combination whose operator is a free variable, none of its formal parameters can be known since the callee may decide to call it with any actual parameters.

Once these variables are eliminated from the list of variables, the rest are examined to determine which are known at compile time. A variable can be known only if it does not have any backward links, and only has one procedure in its procedure list or one constant in its constants list. If no such variables are found, there are no compile time known variables. If there are any, they are tagged as known, and tagged with their known value. Then they are removed from the backwards links list of all their forward links, since they must already appear in their constants or procedures lists, and the remaining variables are checked again until no more known ones are found. Combinations have known operators if their operator place holders are known variables.

After the known value analysis the information is transformed into the format which the code generator requires, and control is transferred to the code generator phase.

20 CHAPTER 4. THE PROGRAM ANALYZER [This page intentionally left very nearly blank.]

Code Generation

After the analysis and possible source level optimization of a Scheme program, the code generator is invoked to translate the code into assembly language.

The code generator is a major modification of a Scheme compiler written by James S. Miller based on the compiler which appears in [Abelson & Sussmans 85]. The compiler is structured in two levels.

The top level performs a code walk over the expression to be translated. It generates assembly language by using an instruction abstraction provided by the bottom level. The code for the compilation of constants, sequences, conditionals and disjunctions is basically the same as in the initial compiler. The code for procedures, combinations, variable references and assignments and the rest of the special forms has been rewritten to accommodate the different types of procedures and environment frames generated by the compiler and compiled code.

The bottom level contains a collection of data abstractions used by the top level. It generates the abstract assembly language instructions, provides house-keeping, and performs peep-hole optimizations on the code. Peep-hole optimizations are local modifications of the output code which do not change its effect but eliminate useless instructions (for example push/restore pairs and assignment of the value of one register to the same register). Part of the bottom level of the code generator has been rewritten to accommodate some new requirements of the top level and to provide the environment frame abstraction, but it mostly remains unchanged from the original version.

Most of the code in the code generator corresponds to the compilation of variable references and assignments, procedures (lambdas) and combinations.

5.1 Environments and variable references

Compiled procedures use three different kinds of environment frames depending on their type. Stack environments are allocated on a stack. Interpreter compatible environments and compiled environments are allocated on the heap but they differ in the nesting (chaining) mechanism.

1. Interpreter compatible environments are completely equivalent to those produced by the interpreter (in most cases their generation is left to the interpreter). Each such frame contains extra slots used by the interpreter for interactive defines and the closure that created it when the closure was applied. The closure contains an interpreter lambda expression (whose body is a compiled expression) and another interpreter compatible environment, that in which the lambda expression was evaluated. The previous frame is obtained, when needed, from the closure. It is in this way that the lexical scoping of the language is implemented in the interpreter. Of all compiled code only interpreter compatible procedures will use these environments.

2. Compiled environments are chained differently and do not contain the extra slots needed for interactive definitions. Compiled environments are vectors whose first slot contains the previous frame and whose second slot contains the closure which generated the environment when it was applied. Heap closures will generate these frames when applied (called).

3. Stack environments are generated by stack procedures and are not chained. Displays are used for references outside the current frame. The first element of a stack frame is the first argument given to the procedure except when the frame is generated by an intermediate procedure. In this case the first element will be the closure itself.

Displays are a simple mechanism which can provide significant improvements in variable reference time. Displays consist of little arrays^{1} with one slot per compiled stack procedure. Each slot contains the environment pointer of the last invocation of the corresponding procedure while it is still active. The environment pointer of a stack procedure is the contents of the stack pointer at the time the procedure code is entered (through the normal entry point: see below). A callee saves convention is followed for the display slots: a stack procedure first stores in its frame the old contents of its display slot. It then stores its own frame pointer in its display slot and proceeds to execute its body. When a procedure frame is popped, the old contents of the display slot are restored from the procedure’s frame.

Variable referencing and assignment is simple. If the variable is a local variable (formal parameter or local auxiliary), it can be found by an indexed reference off the environment frame pointer. If it is a variable declared in a lexically enclosing stack procedure, the value can be found by doing an indexed reference off the contents of the display slot corresponding to the procedure which declares it. If it is not a stack procedure, the environment of the last lexical closure is found and a normal lookup following the environment chains proceeds from there. If the variable is a free variable, the last interpreter compatible frame is found and then the interpreter is invoked to find the value.

1Displays are not implemented as actual arrays, but fixed locations are used instead. Also there only need to be as many locations as the maximum lexical nesting depth of a program since two frames at the same level can use the same slot. The approach I have taken makes it easier for a debugger to examine the information on the stack since it knows where to find the current frame pointers.

5.2 Procedures and environment linkage

Procedures may have up to three entry points which are used when invoking them from different places.

Interpreter compatible procedures are implemented as lambda expressions with a compiled expression as their body. It must be done in this way because the variable lookup mechanism in the interpreter expects to find a lambda expression in the closure and will use it to find the relation between the variable names and their locations in the environment.

Full closures have a first entry point which is the one by which they are entered when invoked from the interpreter. The interpreter leaves the procedure arguments on the stack and the procedure must proceed to reformat its frame if necessary (if it is a heap closure it must create a compiled environment). A combination whose operator is always a constant full closure will invoke it through the second entry point, the compiled call entry point. In this case the combination is said to “know about” its callee. Immediately after the second entry point the display is initialized if the frame is not kept on the heap (the closure is a heap closure). The third entry point bypasses this step and is used for looping.

Partial closures are equivalent to full closures except that they never need to reformat their frame. They only appear as constant operators of combinations, so the caller knows how to prepare the environment. They only have the compiled call and looping entry points.

Open procedures are always called from places that know about them so they assume that their arguments are formatted correctly on the stack. They also have only two entry points with the looping entry point bypassing the display linkage instructions.

5.3 Combinations and tail recursion

Combinations, like all Scheme expressions, may occur in two positions in the code. They may appear as subproblems or as reductions.

An expression occurs as a subproblem of a procedure if the procedure needs the value of the expression to proceed in its computation.^{2}

An expression occurs as a reduction of a procedure if the value returned by the procedure is the value of the expression without further processing. For example, in

   (define (fact n)
     (if (zero? n)
         1
         (* n (fact (-1+ n)))))

the combination which represents the call to fact within its body is a subproblem of fact since the value computed by it is needed by fact to compute its own. However the expression which represents the call to * is a reduction since the value of fact is that returned by * in

   (define (fact n ans)
     (if (zero? n)
         ans
         (fact (-1+ n) (* n ans))))

the recursive call to fact is a reduction since its value is the value returned from fact, however the call to * is a subproblem since fact needs it before it can invoke itself.

A procedure which has a combination as a reduction is said to tail recurse^{3} into the operator of the combination (e.g., fact tail recurses into * in the first example but into itself in the second).

Combinations are dealt with in different ways depending on the position in the code in which they appear and which procedures are the caller and the callee. Ignoring the position in which they appear in the code they are treated according to the knowledge about the procedure being invoked:

• The operator is not known at compile time. The operand and operator expressions are executed and pushed on the stack. The interpreter’s procedure invocation mechanism is then invoked.

• The operator is a primitive procedure. Only the expressions for the operand evaluations are compiled. If the primitive can be open-coded (in-line coded), it is done. If it cannot be open-coded, the primitive routine provided by the interpreter is used.

2The concepts of subproblem and reduction extend in the obvious way to arbitrary expressions.

Thus the predicate expression of a conditional is a subproblem of the conditional, but both the consequent and the alternative expressions are its reductions.

3This use is not standard. Usually tail recursion refers to the special case where a procedure reduces into an invocation of itself, as in the second fact above.

• The operator is a procedure which is known at compile time. The code generator knows the type of procedure being invoked and therefore generates code to construct the appropriate kind of frame where it stores the results of executing the operands. If the callee is a closure, the expression corresponding to the operator is also executed since it will provide the rest of the environment of the callee. The code then branches to the internal entry point of the invoked procedure.

In other languages (such as Algol and Pascal, for example) combinations are treated almost the same way that known procedures are treated above except that a return address is pushed on the stack before branching to the invoked procedure. Procedures pop their frames before returning a value. This should clearly not be the case for Scheme code since procedure calls are used so widely. Other languages do not need to optimize procedure invocation much since they provide other constructs (while and for loops, for example) which can be compiled differently.

In Scheme it is important to treat reductions and subproblem combinations differently. If they were treated in the same way that Algol treats them, the stack would grow arbitrarily large when tail recursing. Loops would not be very efficient in compiled Scheme.

If the environments are constructed on the heap, there is no problem. No part of the stack has to be freed up when tail recursing since there is no information on the stack. The stack is only used to keep information temporarily and to contain return addresses for subproblems. This is in fact how the interpreter operates.

The problem appears when frames are allocated in the stack. Subproblems are treated almost the same way that normal combinations are treated in Algol. Reductions are treated in a very different way. It would be ideal if we could always pop the frame created by a procedure before it reduced into a different one. This is generally not possible since the invoked procedure may be declared within its caller and therefore need the caller’s frame. For example, in

   (define (sum-integers n)
     (define (loop i result)
       (if (> i n)
           result
           (loop (1+ i) (+ i result))))
     (loop 1 0))

the frame created by sum-integers cannot be popped when initially invoking loop since it is the frame where n is to be found.

The callee must be able to pop all frames above itself which were left around only because they were needed by itself. It may appear that the callee could know how many frames to pop, but this is not a static decision; it cannot be decided, in general, at compile time. For example, in

   (define (foo x)
     (define (bar y) (* x (+ x y)))
     (if (zero? x) (bar 1) (+ x (bar 5))))

if x is zero?, foo’s frame should be popped when bar tail recurses into *. Otherwise bar should not pop foo’s frame since foo will need it when it recovers control.

A first approach to a solution would be to have the outer procedure pop its own frame. Each procedure gives its callees a popper routine as an argument. The popper routine is a little piece of code which knows how to pop the caller’s frame if necessary. A popper passed when the combination was a subproblem would not pop the frame, but a reduction popper would pop the frame and call the popper of its caller. This solution is, however, not correct. In the following case

   (define (foo x)
     (define (bar y)
       (* x y))
     (define (quux n)
       (define (grok m)
         (if (= x m) (* n m) (bar 7)))
       (if (zero? n)
           (grok 4)
           (+ x (grok n))))
     (quux (+ x 3)))

bar cannot know how many frames to pop when it reduces into *. The call to bar may have resulted from the expression (grok 4) in which case it would have to pop everything. But it may have resulted from (+ x (grok n)) in which case it would only have to pop itself.

The popper routine passed to grok cannot know how many frames to pop when grok is reduced. If grok reduces into * it would have to call the popper routine which foo gave quux. In the other case it should not, but this can only be determined at runtime.

The problem has a dynamic (runtime) component since the sequence of invocations cannot in general be determined at compile time. The rest of this chapter deals with the solution to this problem.

The overall idea is that each procedure which cannot pop its frame gives a popper which knows how to pop its frame to the callee. This popper is not fixed as in the above strategy, but dynamically decides whether to pop the frame or not depending on the parameters it receives as arguments. In the case of subproblems the popper does nothing but remove itself (the popper) when going off to closures, primitives, or the interpreter, since all frames have been removed at this point. A reductive combination, unless it can determine exactly how many frames to pop (when calling a procedure declared at the same lexical level), sends a message up the stack to let each procedure decide if it should pop its frame. Since the message contains the number of lexical levels which it would like to pop, it will be stopped at the appropriate place if all procedures whose frames are currently on the stack had reduced. If there are any subproblems, they will stop the message from propagating, and closures also stop the message after popping themselves since there are no stack frames in their lexical chain above them on the stack.

The details of the implementation of the above idea are rather intricate:

Each open procedure receives a popper routine as an additional implicit parameter. Popper routines are procedures of three parameters (which are left in registers for fast reference and modification). These parameters, initially passed by the tail recursing procedure, are as follows:

• A flag which can take one of three values:

1. value (0) the procedure is not tail recursing but returning a value.

2. apply (1) the procedure is tail recursing into a procedure that does not share any stack frames with it (e.g., a closure, a primitive or the interpreter).

3. stack (−1) the procedure is tail recursing into a procedure which shares part of its stack environment.

• A number specifying the number of frames the tail recursing procedure would like to pop. It depends only on the lexical distance between the caller and the callee (the number of frames between the declaration of the caller and the declaration of the callee). This parameter is of interest only when the flag is

     stack.

• An address where processing of the application continues after the frames have been popped. It is not used when the flag is value since there is no further processing.

Popper routine entry points are placed on the stack by the caller procedure, above the stack frame of the callee. They call the previous popper by executing a subroutine return instruction. When poppers are entered, their entry point has been popped from the stack. Popper routines are of three different types:

1. Subproblem Popper When invoked it checks the value of the flag. If the flag is value, the subproblem computation has been finished and it returns (the return address for the subproblem is immediately above the popper in the stack). If the flag value is apply, it jumps to its third argument. If the flag value is stack, it re-pushes its entry on the stack and jumps to its third argument.

2. Closure Popper When invoked it pops the frame of the procedure that pushed it. It then checks the value of the flag. If it is value it returns. Otherwise it jumps to its third argument.

3. Pop-Through Popper When invoked it pops its frame and checks the flag.^{4} If it is apply or value it calls the popper above itself on the stack. If the flag is stack it decrements its second argument and if the result is 0 it jumps to its third argument. If it is not 0 it calls the popper above itself.

What follows is a detailed description of each case. If the combination occurred in a subproblem position, the action depends only on which type of procedure is being invoked:

• If the invoked procedure is an intermediate procedure or a primitive, or if the interpreter is being invoked, first a return address is pushed on the stack. Then the operands and the operator are evaluated and pushed on the stack and a jump is done to the desired place.

• If the invoked procedure is a known heap closure, first a return address is pushed on the stack. Then an environment frame is allocated from the heap. The operands and the operator are evaluated and stored in the new frame and then the code jumps to the invoked procedure.

• If the invoked procedure is an open procedure, the return address is pushed on the stack, a subproblem popper is pushed, the arguments are evaluated and pushed on the stack, and the code jumps to the invoked procedure.

Combinations in reduction position are considerably more complicated. The action taken depends on the nature of the caller and the callee:

The caller is a heap closure

• The callee is a known heap closure. A frame is allocated from the heap and the operands and operator are evaluated into its slots. Then the code jumps to the invoked procedure.

• The callee is an intermediate procedure, a primitive, or the interpreter. The operands are evaluated and pushed on the stack and the code jumps to the desired place.

• The callee is an open procedure. This case is not possible. Open procedures are declared only in other open procedures or in intermediate procedures.

4There is actually an optimization in this case. When the flag is apply or value the number passed initially is infinity (actually the largest positive integer) and Pop-through poppers only need to decrement test and branch.

The caller is an intermediate procedure

• The callee is a known heap closure. A frame is allocated from the heap and the operands and operator are evaluated into its slots. Then the caller’s frame is removed from the stack and a jump is done to the invoked procedure.

• The callee is an intermediate procedure, a primitive, or the interpreter. The operands are evaluated into temporary registers and then the stack frame is reused. The code then jumps to the invoked procedure (or the interpreter’s entry point).

• The callee is an open procedure. It must then be a child of the caller and therefore it needs the calling frame. A closure popper is pushed on the stack. The operands are evaluated and pushed on the stack and a jump is done to the right place.

The caller is an open procedure

• The callee is a known heap closure. A frame is allocated from the heap and the operands and operator are evaluated into it. Then an APPLY message is sent up the stack, and an address where the current procedure will continue processing the application. When the poppers return control a jump is done to the invoked procedure.^{5}

• The callee is an intermediate procedure, a primitive, or the interpreter. The operands are evaluated into temporary registers. The local frame is popped and an APPLY message is sent up the stack. When the poppers return control, the temporary registers are pushed on the stack and the code jumps to the invoked procedure or the interpreter.

• The callee is an open procedure. There are four subcases:

1. The callee is a child of the caller. A Pop-through popper is pushed on the stack, the operands are evaluated and pushed on the stack, and the code jumps to the callee.

2. The callee is the same procedure as the caller. This case is really a loop. The operands are executed into temporary registers or their appropriate locations in the frame, and the code jumps to its own looping entry.

5The entry point of the callee should be passed in the message, and then the poppers would return directly to the callee.

3. The callee is a sibling^{6} of the caller. The frame is reused in the same way as when looping but the normal entry point is used instead of the looping entry point.

4. The callee is an ancestor or the sibling of an ancestor of the caller. The operands are evaluated into temporary registers, a STACK message is sent up the stack with the lexical distance between callee and caller. When the popper routines return, the operands are pushed on the stack and control is transferred to the callee.

Control may permanently leave a procedure other than through reduction. For example, by returning the value of a variable. When open procedures return, there will be frames above them in the stack. These frames must be eliminated in order to find the return address of the procedure whose subproblem ultimately reduced into an invocation of the current procedure. Procedure value returns are handled as follows:

• The procedure is a heap closure. It just does a subroutine return.

• The procedure is an intermediate procedure. The local frame is popped and a subroutine return is done.

• The procedure is an open procedure. The local frame is popped and a value message is sent up the stack.

The above case analysis handles all possible cases of procedure application and return, but it may seem unclear why the algorithm works. It works because of the following observation: If the frames of two siblings are on the stack at the same time, the one whose frame is above must be waiting for a subproblem completion. If it had reduced it would have popped its frame from the stack before jumping. Therefore if the number of frames in the stack is greater than the lexical nesting of a procedure (sent in the tail recursion message), there must be pending subproblem completions which will stop the message. But the frames which do not now receive the message are precisely those that the procedures awaiting subproblem completion need to proceed their computation.

An inductive argument can be used to prove correctness:

• When there are only frames corresponding to reduction, the algorithm works because of the above observation. The number of frames on the stack must be precisely the lexical nesting level of the procedure being executed. When a stack tail recursion message is sent the correct number of frames will be popped. If a value or apply message is sent, all of the frames including the closure will be popped and the message will stop.

6Siblings are procedures declared within the same outer procedure, each procedure being a sibling of at least itself.

• Now assume that all frames above the current frame correspond to reductions and this frame corresponds to a procedure awaiting subproblem completion. Since the algorithm works for the purely tail recursive case, the frames above the current one correspond to the ancestors of the current one. These are precisely the frames needed for the current procedure to proceed. They are also precisely the frames that this procedure, or whoever it tail recurses into, will request to pop when a value is computed or a final reduction into a primitive or the interpreter is reached (again by the above case). But now if a frame below the current one sends a stack tail recursion message, these frames should not be popped, so the correct frames are popped by stopping the message from propagating when it reaches this point. If a value message is received, the subproblem is done and computation can proceed at the current level. If an apply message is received, the subproblem expression is reducing into a procedure which will normally return when done (since it shares no frames with this one) and the only information left on the stack after removing the popper routine will be precisely that needed to proceed.

• This same argument can now be used to prove that the second frame awaiting subproblem completion will not be popped before it must nor will it keep extra frames around, and so on inductively.

• Now correctness is guaranteed by induction and by the fact that when the first expression is executed all the frames on the stack (none) correspond to tail recursion.

The rest of the code generator is rather trivial.

32 CHAPTER 5. CODE GENERATION [This page intentionally left very nearly blank.]

Conclusions and Comparisons with Other Work

6.1 Conclusions

Liar accomplishes the two goals which were set in its design:

1. It recognizes the cases where Scheme programs are Algol-like and generates code similar to what an Algol compiler would.

2. It is abstract enough that it should be able to be modified easily to generate code for a large variety of machine architectures.

It copes with all the problems that the compilation of a language like Scheme presents, and after suitable small modifications, it should provide the core for a usable working Scheme compiler.

No code produced by Liar has yet been run on the target machine. The interpreter must be changed to be able to call compiled code and this has not yet been done. There are, therefore, no real performance measurements of code produced by Liar. A rough estimate of the speed of the output code can be made, and in certain cases the improvement factor over the interpreted version seems to be in the order of 15.

The possible modifications discussed in chapter 7 should drive this figure higher and make Scheme a usable language for a variety of tasks.

6.2 Comparisons with Rabbit

The main outstanding work along the lines of the present thesis is Rabbit [Steele 78]. No description of a Scheme compiler would be complete without a comparison between it and Rabbit.

34 CHAPTER 6. CONCLUSIONS AND COMPARISONS WITH OTHER WORK

Rabbit is a complicated optimizing compiler. As such it is very much concerned with transformations it can apply to the code to be compiled until the resulting program is as simple and fast as possible. The optimizations are done at source level by using an alternate representation of the code. The program is translated into continuation-passing style (see [Steele & Sussman 76]) and this version of the code is then optimized and translated.

Liaris not an optimizing compiler. It tries to do the minimum amount of work that will still allow it to generate reasonable code. As such it relies much more heavily on the code generator than Rabbit does.

Some issues of code generation are ignored in Rabbit. Ultimate translation into assembly (machine) language is left to the MAC Lisp compiler, since the output of Rabbit is a very simple subset of this language.

While Liar, even with subsequent modifications, may never produce as good code as Rabbit, it should easily become a usable compiler which produces code that performs reasonably.

Future Work

The main pending piece of work is to modify the interpreter so that compiled code can be run. Compiled code can deal with the interpreter but the interpreter cannot currently deal with compiled code. Real performance measurements cannot be obtained until this is done.

The present compiler generates code which can be improved significantly. Most of the changes that can correct these situation do not modify the basic program, however. Minor modifications should provide a compiler which generates high quality code. Some of these possible improvements are:

7.1 Improvements to the Analyzer

There should be some knowledge of pure procedures. Pure procedures are those which do not reference any free variables and therefore need never be closed. If a pure procedure is passed as an argument or returned as a value, the procedure where it is declared need not be closed since the pure procedure does not need to carry its environment of declaration with it.^{1}

Downward funargs should be handled better. Downward funargs are those procedures which are given as arguments to other procedures. They are widely used and are the primary tool of the continuation passing style. In the current compiler, all of them are made into full closures since they are used as arguments. There are frequent special cases, however, where there is no need for this. If the procedure which receives them as arguments invariably calls them, the downward funargs can be viewed as specifying a return to the caller of their caller. If viewed as such, their call can be compiled into a subroutine return after placing their arguments in the appropriate places. The call which gave them as arguments can then be viewed as a subroutine call. For example, in

1Primitives can be viewed as pure procedures which are available in a library.

   (define (cps-fib n)
     (define (fib n cont)
       (if (zero? n)
           (cont 0 1)
           (fib (-1+ n)
                (lambda (n m) (cont m (+ n m))))))
     (fib n (lambda (n m) n)))

all procedural parameters can be interpreted as the action to take after multiple value returns. A more complete analysis could recognize them as such and provide this knowledge to the code generator to translate them accordingly. An important special case of this is any call to the system procedure catch.

Combinations with variable operators should be handled better. Combinations with more than one possible operator are handled by giving control to the interpreter to perform the procedure application. Procedures which would not need to be closures otherwise, are tagged as closures when they appear as operators of these combinations. If all possible operators of a combination are declared at the same lexical level, which is usually the case, the compiler can generate better code to perform the application. For example, the current analyzer will make fact and fib be translated as closures in

   (define (weird-function n)
     (define (fib n)
       (if (< n 2)
           n
           (+ (fib (-1+ n))
              (fib (- n 2)))))
     (define (fact n)
       (if (zero? n)
           1
           (* n (fact (-1+ n)))))
     ((if (odd? n) fact fib) n))

but there is clearly no need for this.

Some constant folding should be done after the analysis. The eval/apply simulation provides all knowledge that can be determined at compile time about variables. This knowledge can be used to determine which combinations can be evaluated at compile-time and which conditional branches are fixed therefore eliminating some runtime computation.

7.2 Improvements to the code generator

It is simple to add a push/pop optimizer to the code generator. Procedures preserving and append-instruction-sequence should be redefined to postpone the generation of the push/pop pairs until all the blocks in each sequence are available. It is then trivial to examine the registers used and required by each element and generate the minimum number of push and pop instructions. This can provide almost as good push/pop performance as that obtained if racks were used instead of stacks. See [Steele & Sussman 80] for a description of racks and dynamic runtime push/pop optimization.

The order of argument evaluation in loops should be optimized. Certain arguments do not need the complete frame to be evaluated and can therefore be evaluated after some variables have already been assigned the new values. This can reduce the number of temporary registers needed and the amount of register shuffling. This reordering is not always possible since in the presence of side effects it might make the code behave differently. However, it is considered bad Scheme style to write code which depends on the order of argument evaluation.

Invocations of stack procedures declared at the same lexical level should use the looping entry point. This can be done if they use the same display slot.

Stack procedures which have no subprocedures (simple procedures) should not store their environment pointer in the display slot or restore it on return, since they can reference their frame from the environment register and no other procedures will need their internal frame.

Simple procedures should take their arguments in processor registers to increase the speed of reference and assignment. This should improve the performance of tight loops which do not usually include inner procedures.

An assembly language level optimizer should be written to improve loops. Loops are translated as unconditional transfers to the entry point. It is usually the case that there is a conditional branch in the body of the loop. A topological transformation of the code (rotation of the loop) can be performed to eliminate the unconditional branch. Procedures called from only one place in the code should be located where the jump to their code appears in order to eliminate the extra jump instruction. Both these transformations can be left to an assembly language optimizer which deals only with the control structure of the program.

More primitives should be in-line coded. Small primitives for which the overhead of the call is large in proportion to their execution time should all be in-line coded. Fixnum arithmetic primitives are among these.

38 CHAPTER 7. FUTURE WORK [This page intentionally left very nearly blank.]

Bibliography

[Abelson & Sussmans 85] Harold Abelson and Gerald Jay Sussman with Julie Sussman Structure and Interpretation of Computer Programs (Fifth Printing) (The MIT Electrical Engineering and Computer Science Series) The MIT Press, 1985

[Hanson 84] Chris Hanson Scode Description Unpublished internal memo of the MIT AI Scheme Team, 1984

[Hanson 91] Chris Hanson and the MIT Scheme Team MIT Scheme Reference Manual MIT AI-TR-1281, Jan 1991

[Moses 70] Joel Moses The function of FUNCTION in Lisp MIT AI Memo No.199, Jun 1970

[Rees & Clinger 86] Jonathan Rees and William Clinger (Editors) Revised^{3} Report on the Algorithmic Language Scheme MIT/AI/Memo 848a or Indiana University CS/TR 174 or ACM SIGPLAN Notices, Vol.21 No.12, Dec 1986

[Steele 76] Guy Lewis Steele Jr. LAMBDA: The Ultimate Declarative MIT AI Memo No.379, Dec 1976 [Steele 77]

Guy Lewis Steele Jr. Debunking the “Expensive Procedure Call” Myth or, Procedure Call Implementations Considered Harmful or, LAMBDA: The Ultimate GOTO MIT AI-TR-443, Oct 1977 and In ACM Conference Proceedings, pp.153–162, 1977

[Steele 78] Guy Lewis Steele Jr. Rabbit: A Compiler for Scheme (A Study in Compiler Optimization) MIT S.M. Thesis, MIT AI-TR-474, May 1978

[Steele & Sussman 75] Guy Lewis Steele Jr. and Gerald Jay Sussman Scheme: An Interpreter for Extended Lambda Calculus MIT AI Memo No.349, Dec 1975

[Steele & Sussman 76] Guy Lewis Steele Jr. and Gerald Jay Sussman LAMBDA: The Ultimate Imperative MIT AI Memo No.353, Mar 1976

[Steele & Sussman 80] Guy Lewis Steele Jr. and Gerald Jay Sussman The Dream of a Lifetime: A Lazy Scoping Mechanism MIT AI Memo No.527, Nov 1979 and In Conference Record of the 1980 Lisp Conference, pp.163–172, 1980

Appendix A

Scode Description and Source Code

A.1 Brief Scode Description

The following are some important Scode structures. For a complete description see [Hanson 84].

Variable Corresponds to a variable in a program. The only component is its name.

Assignment Corresponds to the special form set!. It has two components: the variable being assigned, and the expression whose value will be the new value of the variable.

Definition Corresponds to the special form define. Its two components are the symbol being defined and the value which the symbol will receive.

Access Corresponds to the special form access. Its two components are the symbol being accessed and an expression whose value will provide the environment where the symbol will be looked up.

The-Environment Corresponds to the the-environment special form. When evaluated it returns the environment where evaluated.

In-Package Corresponds to the in-package special form. It consists of two expressions. The environment expression provides the environment where the other expression will be evaluated. This expression will provide the value of the in-package expression.

Disjunction Corresponds to the special form disjunction. It consists of a predicate expression whose will be returned if it is not false, and an alternative expression which will be evaluated otherwise.

Conditional Corresponds to the if special form. It consists of predicate, consequent, and alternative expressions.

Sequence Corresponds to the special form sequence. It has any number of components, called actions, which are evaluated sequentially in left-to-right order.

Combination Corresponds to a procedure invocation. It contains an operator expression and any number of operands expressions.

Lambda Corresponds to the special form lambda. It consists of a name, a list of required formal parameters, a list of auxiliary variable names, an optional tail argument (which will receive all the optional extra arguments), and a body expression.

A.2. ANALYZER SOURCE CODE 43

A.2 Analyzer Source Code